package one;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
 * <p>
 * For example:
 * Given binary tree {3,9,20,#,#,15,7},
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * return its zigzag level order traversal as:
 * <p>
 * [
 * [3],
 * [20,9],
 * [15,7]
 * ]
 * <p>
 * =========================================
 * <p>
 * Solution:
 * <p>
 * <p>
 * /**
 * Definition for binary tree
 * public class one.TreeNode {
 * int val;
 * one.TreeNode left;
 * one.TreeNode right;
 * one.TreeNode(int x) { val = x; }
 * }
 */



public class Day07_Binary_Tree_Zigzag_Level_Order_Traversal {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (root != null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        int cur = 1;
        int next = 0;
        int level = 0;
        queue.add(root);
        List<Integer> adds = new ArrayList<Integer>();
        if (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            cur--;
            adds.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
                next++;
            }
            if (node.right != null) {
                queue.add(node.right);
                next++;
            }
            if (cur == 0) {
                if (level % 2 == 0) {
                    res.add(new ArrayList<Integer>(adds));
                } else {
                    ArrayList<Integer> tmp = new ArrayList<Integer>();
                    for (int i = adds.size() - 1; i > 0; i--) {
                        tmp.add(adds.get(i));
                    }
                    res.add(tmp);
                }
                adds.clear();
                cur = next;
                next = 0;
                level++;
            }
        }
        return res;
    }
}
